This invention relates to compression of images, in particular, to compression methods employing symbol matching.
A standard 8.5 by 11 inch page, when scanned as a binary image at 300 dots per inch (DPI), comprises over 8,000,000 bits of information-about a megabyte. The same page, when scanned at 200 DPI, the scan rate of fax fine mode, comprises almost half a megabyte of information. Because of the large capacity needed to store such images, some sort of image compression is typically implemented in image storage and transmission devices.
One current standard method for binary image compression, in widespread use as the standard for facsimile transmission, is the CCITT-3 standard. This is a lossless binary image compression algorithm based on Huffman encoding of a run-length encoding of the image. The CCITT-3 standard typically compresses an image by an order of magnitude by taking into account first-order statistical regularities in the lengths of runs. Thus, a 300 DPI image may be compressed from a megabyte to 100 kilobytes.
Symbol matching can be used to increase compression ratios for binary images which consist primarily of machine-printed text. Such text is characterized by many small regions of connected black pixels, representing characters, surrounded by white pixels. A typical document might use only a few hundred different characters representing the letters of the alphabet in upper- and lowercase in a few different type faces (e.g., Times and Helvetica) and type styles (e.g., plain, bold, italics). In compression techniques employing symbol matching, similar characters are grouped, and their description as an array of black pixels is represented only once as a template. The entire binary image is represented as a sequence of templates along with references to their positions within the image. In this way, the representation contains far fewer bits than the original image. The amount of compression that can be achieved using symbol matching depends on how many characters are matched, how the templates are represented, and how the character positions are represented.
Unfortunately, characters that appear similar to the human eye are not usually pixel-identical. The printing method, subsequent photocopying, and, most importantly, the scanning process itself introduce error into the original image. An example is illustrated in FIG. 1, which depicts two instances of the letter "b" in 12 point Courier scanned at 200 DPI. The error pixels are also shown. In order for a symbol matching scheme to significantly contribute to binary image compression, error between two characters must be allowed, but bounded. Some notion of the matching of two characters based on perceptual similarity is needed for this purpose. Furthermore, since the matching characters are not all identical, a way of defining a template from the matching characters is required. Since such a template is necessarily not identical to all of the characters used to define it, the representation by templates does not encode the image perfectly. But since the characters vary only slightly in appearance from the template, the difference is not perceptible.
The success of symbol matching in binary image compression hinges crucially on how similarity of two characters is judged (how characters are matched). A matching metric allowing large pixel differences between characters is prone to substitution errors. For example, as illustrated in FIG. 2, an instance of a "b" and an instance of an "h" in the same font and size can have a relatively small pixel error. If they are matched, the reconstructed image will be riddled with errors. On the other hand, if the matching metric is too stringent, then multiple instances of the same character will not be matched and little compression will be achieved.
The use of symbol matching in binary image compression dates back to at least 1974 (see "A means for achieving a high degree of compaction on scan-digitized-printed text," by R. N. Ascher and G. Nagy, in IEEE Transactions on Computers, 23(11):1174-1179, Nov. 1974). Since then, a variety of compression systems employing symbol matching have been proposed. (See "Combined symbol matching facsimile data compression system," by W. K. Pratt et al., in Proceedings of the IEEE, 68(7):786-796, July 1980, and U.S. Pat. Nos. 4,091,424, 4,288,782, 4,410,916, 4,463,386, 4,499,499, and 4,606,069.) The present invention is a compression method employing a substantially improved matching process, as well as other improved features which increase the compression ratio.